Add two numbers represented by linked lists



In [1]:

    
class Node():
    def __init__(self, value, Next=None):
        self.value = value
        self.next = Next
    def __str__(self):
        if self.next == None:
            return str(self.value)
        return str(self.value) + '-' + self.next.__str__()



In [12]:

    
def getSize(node):
    count = 0
    while node != None:
        count += 1
        node = node.next
    return count
        
def _add(node0, size0, node1, size1):
    
    if node0 == None:
        return None, 0
    
    if size0 > size1:
        node, carry = _add(node0.next, size0 - 1, node1, size1)
    
        new = node0.value + carry
    else:
        node, carry = _add(node0.next, size0 - 1, node1.next, size1 -1)
        
        new = node0.value + node1.value + carry
    
    carry = new//10        
    new = new%10
    print(new, carry)
    return Node(new, node), carry

def add(node0, size0, node1, size1):
    
    node, carry = _add(node0, size0, node1, size1)
    if carry > 0:
        node = Node(1, node)
    
    return node

a = Node(1, Node(2, Node(5, Node(6, Node(3, None)))))
b = Node(8, Node(4, Node(2, None)))

print(add(a, getSize(a), b, getSize(b)))

2.1 Remove Dups:

Write code to remove duplicates from an unsorted linked list. FOLLOW UP How would you solve this problem if a temporary buffer is not allowed?



In [24]:

    
List = Node(1, Node(2, Node(3, Node(4, Node(4, Node(4, Node(3, Node(2, Node(1)))))))))

def remove_dups(List):
    marks = {}
    cur = List
    prev = None
    while cur != None:
        if marks.get(cur.value, 0) == 0: # not duplicated
            marks[cur.value] = 1
        else: # duplicated
            prev.next = cur.next
            cur = prev
                
        prev = cur
        cur = cur.next

print('input:' + str(List))
remove_dups(List)
print('output:' + str(List))









    



input:1-2-3-4-4-4-3-2-1
output:1-2-3-4



In [34]:

    
def remove_dups_wo_buffer(List):
    cur0 = List
    while cur0 != None:
        prev = cur0
        cur1 = cur0.next
        while cur1 != None:
            if cur1.value == cur0.value:
                prev.next = cur1.next
                cur1 = prev
            prev = cur1
            cur1 = cur1.next
        
        cur0 = cur0.next
        
List = Node(1, Node(2, Node(3, Node(4, Node(4, Node(4, Node(3, Node(2, Node(1, Node(3, Node(2)))))))))))

print('input:' + str(List))
remove_dups_wo_buffer(List)
print('output:' + str(List))









    



input:1-2-3-4-4-4-3-2-1-3-2
output:1-2-3-4

2.2 Return Kth to Last:

Implement an algorithm to find the kth to last element of a singly linked list.



In [37]:

    
List = Node(1, Node(2, Node(3, Node(4, Node(4, Node(4, Node(3, Node(2, Node(1, Node(3, Node(2)))))))))))

def kth_to_last(List, k):
    cur = List
    size = 0
    while cur != None:
        size += 1
        cur = cur.next
    if size < k:
        return None
    
    cur = List
    for _ in range(size - k):
        cur = cur.next
    return cur.value

print(kth_to_last(List, 4))



In [40]:

    
def kth_to_last(head, k, i):

    if head == None:
        return None
    
    node = kth_to_last(head.next, k, i)
    i[0] = i[0] + 1
    if i[0] == k:
        return head
    else:
        return node
    
print(kth_to_last(List, 4, [0]))



In [ ]: